package com.ls.que81_85;

import java.util.Stack;

/**
 * @author ：ls
 * @date ：2022/3/5 10:17
 * @description：...
 */
public class LargestRectangleArea {
    public static int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        int max_area = 0, val = 0, left_index=-1;
        for (int i=1; i<heights.length; i++){
            while (!stack.empty() && heights[i] < heights[stack.peek()]){
                val = heights[stack.pop()];
                while (!stack.empty() && val == heights[stack.peek()]){
                    stack.pop();
                }
                if (stack.empty()){
                    left_index = -1;
                }else {
                    left_index = stack.peek();
                }
                max_area = Math.max(max_area, (i - left_index - 1) * val);
            }
            stack.push(i);
        }
        val = heights[stack.pop()];
        while (!stack.empty()){
            max_area = Math.max(max_area, (heights.length - 1 - stack.peek()) * val);
            val = heights[stack.pop()];
        }
        max_area = Math.max(max_area, val * heights.length);
        return max_area;
    }

    public static void main(String[] args) {
        System.out.println(largestRectangleArea(new int[]{2, 4}));
    }
}
